#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    struct cmp
    {
        bool operator()(pair<int, int> a, pair<int, int> b)
        {
            if (a.first == b.first) return a.second > b.second;
            else return a.first > b.first;
        }
    };
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> heap;
        int n = nums.size();
        for (int i = 0; i < n; i++) heap.push({ nums[i], i });
        while (k--)
        {
            auto pair = heap.top(); heap.pop();
            nums[pair.second] *= multiplier;
            heap.push({ nums[pair.second], pair.second });
        }
        return nums;
    }
};